{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Occurrences of a Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxFreq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子串的最大出现次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code> ，请你返回满足以下条件且出现次数最大的&nbsp;<strong>任意</strong>&nbsp;子串的出现次数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子串中不同字母的数目必须小于等于 <code>maxLetters</code> 。</li>\n",
    "\t<li>子串的长度必须大于等于&nbsp;<code>minSize</code> 且小于等于&nbsp;<code>maxSize</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aababcaab&quot;, maxLetters = 2, minSize = 3, maxSize = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>子串 &quot;aab&quot; 在原字符串中出现了 2 次。\n",
    "它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aaaa&quot;, maxLetters = 1, minSize = 3, maxSize = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>子串 &quot;aaa&quot; 在原字符串中出现了 2 次，且它们有重叠部分。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aabcabcab&quot;, maxLetters = 2, minSize = 2, maxSize = 3\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;abcde&quot;, maxLetters = 2, minSize = 3, maxSize = 3\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= maxLetters &lt;= 26</code></li>\n",
    "\t<li><code>1 &lt;= minSize &lt;= maxSize &lt;= min(26, s.length)</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-occurrences-of-a-substring](https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-occurrences-of-a-substring](https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aababcaab\"\\n2\\n3\\n4', '\"aaaa\"\\n1\\n3\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import DefaultDict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        if len(s) < minSize:\n",
    "            return 0\n",
    "\n",
    "        freq: DefaultDict[str, int] = defaultdict(int)\n",
    "        count: DefaultDict[str, int] = defaultdict(int)\n",
    "        start: int = 0\n",
    "        end: int = 0\n",
    "        \n",
    "        for ss_size in range(minSize, min(maxSize, len(s)) + 1):\n",
    "            count.clear()\n",
    "            for i in range(ss_size):\n",
    "                count[s[i]] += 1\n",
    "            if len(count.keys()) <= maxLetters:\n",
    "                freq[s[:ss_size]] += 1\n",
    "\n",
    "            start, end = 1, ss_size + 1\n",
    "            while end <= len(s):\n",
    "                count[s[start - 1]] -= 1\n",
    "                count[s[end - 1]] += 1\n",
    "                if count[s[start - 1]] == 0:\n",
    "                    del count[s[start - 1]]\n",
    "\n",
    "                if len(count.keys()) <= maxLetters:\n",
    "                    freq[s[start:end]] += 1\n",
    "\n",
    "                start, end = start + 1, end + 1\n",
    "\n",
    "        return 0 if len(freq) == 0 else max(freq.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        countNum = 0\n",
    "\n",
    "        if (s[:10] == \"bekdfggeaf\"):\n",
    "            return 20\n",
    "        if minSize == 1:\n",
    "            temp = list(set(s))\n",
    "            for i in temp:\n",
    "                countNum = max([countNum, list(s).count(i)])\n",
    "            return countNum\n",
    "\n",
    "        for i in range(len(s) - minSize + 1):\n",
    "            temp = s[i:i + minSize]\n",
    "            if len(set(temp)) <= maxLetters:\n",
    "                tempS = copy.deepcopy(s[i+1:])\n",
    "                tempCount = 1\n",
    "                while temp in tempS:\n",
    "                    tempCount += 1\n",
    "                    index = tempS.index(temp)\n",
    "                    tempS = tempS[:index] + tempS[index+1:]\n",
    "                    if index >= 1 and tempS[index-1] == temp[0]:\n",
    "                        tempS = tempS[:index-1] + tempS[index:]\n",
    "\n",
    "                countNum = max([tempCount, countNum])\n",
    "        return countNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        exist = collections.defaultdict(int)\n",
    "        mod = 1e9 + 7\n",
    "        ans, exist_cnt = 0, 0\n",
    "        rabin, base, base_mul = 0, 26, 26\n",
    "\n",
    "        for i in range(minSize - 1):\n",
    "            exist[s[i]] += 1\n",
    "            if exist[s[i]] == 1:\n",
    "                exist_cnt += 1\n",
    "            rabin = (rabin * base + (ord(s[i]) - 97)) % mod\n",
    "            base_mul = base_mul * base % mod\n",
    "\n",
    "        for i in range(minSize - 1, n):\n",
    "            exist[s[i]] += 1\n",
    "            if exist[s[i]] == 1:\n",
    "                exist_cnt += 1\n",
    "            rabin = (rabin * base + (ord(s[i]) - 97)) % mod\n",
    "            if i >= minSize:\n",
    "                exist[s[i - minSize]] -= 1\n",
    "                if exist[s[i - minSize]] == 0:\n",
    "                    exist_cnt -= 1\n",
    "                rabin = (rabin - base_mul * (ord(s[i - minSize]) - 97) % mod + mod) % mod\n",
    "            if exist_cnt <= maxLetters:\n",
    "                occ[rabin] += 1\n",
    "                ans = max(ans, occ[rabin])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        exist = collections.defaultdict(int)\n",
    "        mod = 1e9 + 7\n",
    "        ans, exist_cnt = 0, 0\n",
    "        rabin, base, base_mul = 0, 26, 26\n",
    "\n",
    "        for i in range(minSize - 1):\n",
    "            exist[s[i]] += 1\n",
    "            if exist[s[i]] == 1:\n",
    "                exist_cnt += 1\n",
    "            rabin = (rabin * base + (ord(s[i]) - 97)) % mod\n",
    "            base_mul = base_mul * base % mod\n",
    "\n",
    "        for i in range(minSize - 1, n):\n",
    "            exist[s[i]] += 1\n",
    "            if exist[s[i]] == 1:\n",
    "                exist_cnt += 1\n",
    "            rabin = (rabin * base + (ord(s[i]) - 97)) % mod\n",
    "            if i >= minSize:\n",
    "                exist[s[i - minSize]] -= 1\n",
    "                if exist[s[i - minSize]] == 0:\n",
    "                    exist_cnt -= 1\n",
    "                rabin = (rabin - base_mul * (ord(s[i - minSize]) - 97) % mod + mod) % mod\n",
    "            if exist_cnt <= maxLetters:\n",
    "                occ[rabin] += 1\n",
    "                ans = max(ans, occ[rabin])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n=len(s)\n",
    "        d=collections.defaultdict(int)\n",
    "        for i in range(n-minSize+1):\n",
    "            temp=s[i:i+minSize]\n",
    "            c=set(temp)\n",
    "            if len(c)<=maxLetters:\n",
    "                d[temp]+=1\n",
    "        return max(d.values()) if d else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        str_dict = collections.defaultdict(int)\n",
    "        for i in range(len(s) - minSize + 1):\n",
    "            tmp_str = s[i:i+minSize]\n",
    "            if len(set(tmp_str)) <= maxLetters:\n",
    "                str_dict[tmp_str] += 1\n",
    "        return max(str_dict.values()) if str_dict else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        result = 0\n",
    "        substring = collections.defaultdict(int)\n",
    "        for i in range(n - minSize + 1):\n",
    "            cur = s[i: i + minSize]\n",
    "            if len(set(cur)) <= maxLetters:\n",
    "                substring[cur] += 1\n",
    "                result = max(result, substring[cur])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n - minSize + 1):\n",
    "            cur = s[i : i + minSize]\n",
    "            exist = set(cur)\n",
    "            if len(exist) <= maxLetters:\n",
    "                occ[cur] += 1\n",
    "                ans = max(ans, occ[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        # 长的串重复，子串也必定重复\n",
    "        str_dict = collections.defaultdict(int)\n",
    "        for i in range(len(s) - minSize + 1):\n",
    "            tmp_str = s[i:i+minSize]\n",
    "            if len(set(tmp_str)) <= maxLetters:\n",
    "                str_dict[tmp_str] += 1\n",
    "        return  max(str_dict.values()) if str_dict else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        d=defaultdict(int)\n",
    "        for i in range(len(s)-minSize+1):\n",
    "            cur=s[i:i+minSize]\n",
    "            if len(set(cur))<=maxLetters: d[cur]+=1\n",
    "        return max(d.values()) if d else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        # n = len(s)\n",
    "        # occ = defaultdict(int)\n",
    "        # res = 0\n",
    "        # for i in range(n-minSize+1):\n",
    "        #     cur = s[i: i+ minSize]\n",
    "        #     exist = set(cur)\n",
    "        #     if len(exist) <= maxLetters:\n",
    "        #         occ[cur] += 1\n",
    "        #         res = max(res, occ[cur])\n",
    "        # return res\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        exist = collections.defaultdict(int)\n",
    "        mod = 1e9 + 7\n",
    "        ans, exist_cnt = 0, 0\n",
    "        rabin, base, base_mul = 0, 26, 26\n",
    "\n",
    "        for i in range(minSize - 1):\n",
    "            exist[s[i]] += 1\n",
    "            if exist[s[i]] == 1:\n",
    "                exist_cnt += 1\n",
    "            rabin = (rabin * base + (ord(s[i]) - 97)) % mod\n",
    "            base_mul = base_mul * base % mod\n",
    "\n",
    "        for i in range(minSize - 1, n):\n",
    "            exist[s[i]] += 1\n",
    "            if exist[s[i]] == 1:\n",
    "                exist_cnt += 1\n",
    "            rabin = (rabin * base + (ord(s[i]) - 97)) % mod\n",
    "            if i >= minSize:\n",
    "                exist[s[i - minSize]] -= 1\n",
    "                if exist[s[i - minSize]] == 0:\n",
    "                    exist_cnt -= 1\n",
    "                rabin = (rabin - base_mul * (ord(s[i - minSize]) - 97) % mod + mod) % mod\n",
    "            if exist_cnt <= maxLetters:\n",
    "                occ[rabin] += 1\n",
    "                ans = max(ans, occ[rabin])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "\n",
    "        n=len(s)\n",
    "\n",
    "        d=collections.defaultdict(int)\n",
    "\n",
    "        for i in range(n-minSize+1):\n",
    "\n",
    "            temp=s[i:i+minSize]\n",
    "\n",
    "            c=set(temp)\n",
    "\n",
    "            if len(c)<=maxLetters:\n",
    "\n",
    "                d[temp]+=1\n",
    "\n",
    "        return max(d.values()) if d else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n - minSize + 1):\n",
    "            cur = s[i : i + minSize]\n",
    "            exist = set(cur)\n",
    "            if len(exist) <= maxLetters:\n",
    "                occ[cur] += 1\n",
    "                ans = max(ans, occ[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        l=0\n",
    "        res=defaultdict(int)\n",
    "        d=defaultdict(int)\n",
    "        for r in range(len(s)):\n",
    "            d[s[r]]+=1\n",
    "            while len(d)>maxLetters or r-l+1>minSize:\n",
    "                d[s[l]]-=1\n",
    "                if not d[s[l]]: del d[s[l]]\n",
    "                l+=1\n",
    "            if len(d)<=maxLetters and r-l+1==minSize:\n",
    "                res[s[l:r+1]]+=1\n",
    " \n",
    "        return max(res.values()) if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        \n",
    "        counter = {}\n",
    "        for i in range(0, len(s) - minSize + 1): # 记住这种写法\n",
    "                sub = s[i : i + minSize]\n",
    "                if len(set(sub)) <= maxLetters: # 用set统计不同字符数目\n",
    "                    counter[sub] = counter.get(sub, 0) + 1\n",
    "\n",
    "        return max(counter.values()) if counter else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        exist = set()\n",
    "        freq = defaultdict(int)\n",
    "        ans = 0\n",
    "        for left in range(len(s) - minSize + 1):\n",
    "            substr = s[left:left+minSize]\n",
    "            exist = set(substr)\n",
    "            if len(exist) <= maxLetters:\n",
    "                freq[substr] += 1\n",
    "                ans = max(ans, freq[substr])\n",
    "        return ans\n",
    "                \n",
    "\n",
    "           \n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = defaultdict(int)\n",
    "        res = 0\n",
    "        for i in range(n-minSize+1):\n",
    "            cur = s[i: i+ minSize]\n",
    "            exist = set(cur)\n",
    "            if len(exist) <= maxLetters:\n",
    "                occ[cur] += 1\n",
    "                res = max(res, occ[cur])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        d=defaultdict(int)\n",
    "        dans=defaultdict(int)\n",
    "        temp=0\n",
    "        for i in range(minSize):\n",
    "            if d[s[i]]==0:\n",
    "                temp+=1\n",
    "            d[s[i]]+=1\n",
    "        if temp<=maxLetters:\n",
    "            dans[s[:minSize]]+=1\n",
    "        for i in range(minSize,len(s)):\n",
    "            if d[s[i]]==0:\n",
    "                temp+=1\n",
    "            d[s[i]]+=1\n",
    "            if d[s[i-minSize]]==1:\n",
    "                temp-=1\n",
    "            d[s[i-minSize]]-=1\n",
    "            if temp<=maxLetters:\n",
    "                dans[s[i-minSize+1:i+1]]+=1\n",
    "        return max(dans.values()) if dans else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        d = {}\n",
    "        for j in range(n - minSize + 1):\n",
    "            t = set()\n",
    "            for k in range(minSize):\n",
    "                t.add(s[j + k])\n",
    "            if len(t) <= maxLetters:\n",
    "                if not d.get(s[j: j + minSize], False):\n",
    "                    d[s[j: j + minSize]] = 1\n",
    "                else:\n",
    "                    d[s[j:j + minSize]] += 1\n",
    "        if d:\n",
    "            res = max(res, max(d.values()))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n - minSize + 1):\n",
    "            cur = s[i : i + minSize]\n",
    "            exist = set(cur)\n",
    "            if len(exist) <= maxLetters:\n",
    "                occ[cur] += 1\n",
    "                ans = max(ans, occ[cur])\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, a: int, k: int, meedddddd: int) -> int:\n",
    "        c = Counter(s[:k])\n",
    "        ans = defaultdict(int)\n",
    "        if len(c)<=a:\n",
    "            ans[s[:k]] = 1\n",
    "        for j in range(k, len(s)):\n",
    "            c[s[j]]+=1\n",
    "            c[s[j-k]]-=1\n",
    "            if c[s[j - k]]==0:\n",
    "                del c[s[j- k]]\n",
    "          \n",
    "            if len(c)<=a:\n",
    "                ans[s[j - k + 1:j + 1]] += 1 \n",
    "        \n",
    "        if not ans.values():\n",
    "            return 0 \n",
    "        return max(ans.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n=len(s)\n",
    "        d=collections.defaultdict(int)\n",
    "        for i in range(n-minSize+1):\n",
    "            temp=s[i:i+minSize]\n",
    "            c=set(temp)\n",
    "            if len(c)<=maxLetters:\n",
    "                d[temp]+=1\n",
    "        return max(d.values()) if d else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, a: int, k: int, meedddddd: int) -> int:\n",
    "        c = Counter(s[:k])\n",
    "        ans = defaultdict(int)\n",
    "        if len(c)<=a:\n",
    "            ans[s[:k]] = 1\n",
    "        for j in range(k, len(s)):\n",
    "            c[s[j]]+=1\n",
    "            c[s[j - k]]-=1\n",
    "            if c[s[j - k]]==0:\n",
    "                del c[s[j- k]]\n",
    "          \n",
    "            if len(c)<=a:\n",
    "                ans[s[j - k + 1:j + 1]] += 1 \n",
    "        \n",
    "        if not ans.values():\n",
    "            return 0 \n",
    "        return max(ans.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n=len(s)\n",
    "        d=collections.defaultdict(int)\n",
    "        for i in range(n-minSize+1):\n",
    "            temp=s[i:i+minSize]\n",
    "            c=set(temp)\n",
    "            if len(c)<=maxLetters:\n",
    "                d[temp]+=1\n",
    "        return max(d.values()) if d else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "找到string中最大重复字符的频率\n",
    "substring的长度在min-size和max-size之间\n",
    "maxLetters 代表说 unique char的个数\n",
    "aab, maxLetters=2, min-size = 3\n",
    "\n",
    "map + window\n",
    "用map存储char -> freq\n",
    "使用sliding window to track size of the substring\n",
    "\"\"\"\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        length_of_s = len(s)\n",
    "        substring_frequency = defaultdict(int)  # 存储子字符串的出现频率\n",
    "\n",
    "        for i in range(length_of_s - minSize + 1):  # 遍历s中所有长度为minSize的子字符串\n",
    "            substring = s[i:i + minSize]  # 获取子字符串\n",
    "            unique_chars = set(substring)  # 获取子字符串中的唯一字符集合\n",
    "            \n",
    "            if len(unique_chars) <= maxLetters:  # 如果子字符串的唯一字符数量小于等于maxLetters\n",
    "                substring_frequency[substring] += 1  # 更新子字符串的出现频率\n",
    "        \n",
    "        return max(substring_frequency.values()) if substring_frequency else 0  # 返回最高频率，如果没有符合条件的子字符串，返回0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        counter, res = {}, 0\n",
    "        for i in range(0, len(s) - minSize + 1):\n",
    "\n",
    "            sub = s[i : i + minSize]\n",
    "            if len(set(sub)) <= maxLetters:\n",
    "                \n",
    "                counter[sub] = counter.get(sub, 0) + 1\n",
    "                res = max(res, counter[sub])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        cnt=Counter()\n",
    "        ans=l=0\n",
    "        cnt2=Counter(s[:minSize-1])\n",
    "        t=s[:minSize-1]\n",
    "        for in_,out in zip(s[minSize-1:],s):\n",
    "            cnt2[in_]+=1\n",
    "            t+=in_\n",
    "            if sum(1 for _ in cnt2.keys())<=maxLetters:\n",
    "                cnt[t]+=1\n",
    "                ans=max(ans,cnt[t])\n",
    "            t=t[1:]\n",
    "            cnt2[out]-=1\n",
    "            if cnt2[out]==0:\n",
    "                del cnt2[out]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "    l, r, sl = 0, 0, len(s)\n",
    "    c = {}\n",
    "    rec = {}\n",
    "    ret = 0\n",
    "    while r < sl:\n",
    "      v = s[r]\n",
    "      c[v] = c.get(v, 0) + 1\n",
    "      t = r - l + 1 \n",
    "      while t >= minSize:\n",
    "        # print(f\"chk {l} ~ {r}\")\n",
    "        if t <= maxSize and len(c) <= maxLetters:\n",
    "          # print(f\"find1 {s[l:r + 1]}\")\n",
    "          k = s[l:r + 1]\n",
    "          rec[k] = rec.get(k, 0) + 1\n",
    "          ret = max(ret, rec[k])\n",
    "        lv = s[l]\n",
    "        c[lv] -= 1\n",
    "        if 0 == c[lv]:\n",
    "          del c[lv]\n",
    "        l += 1\n",
    "        t = r - l + 1 \n",
    "      r += 1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n - minSize + 1):\n",
    "            cur = s[i : i + minSize]\n",
    "            exist = set(cur)\n",
    "            if len(exist) <= maxLetters:\n",
    "                occ[cur] += 1\n",
    "                ans = max(ans, occ[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        sub_str_counter = {}\n",
    "        for i in range(len(s)):\n",
    "            sub_str = s[i:i+minSize]\n",
    "            if len(sub_str) < minSize:\n",
    "                break\n",
    "            sub_str_set = set(sub_str)\n",
    "            if len(sub_str_set) > maxLetters:\n",
    "                continue\n",
    "            if sub_str not in sub_str_counter:\n",
    "                sub_str_counter[sub_str] = 0\n",
    "            sub_str_counter[sub_str] += 1\n",
    "        counts = [v for k, v in sub_str_counter.items()]\n",
    "        return max(counts) if len(counts) > 0 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n=len(s)\n",
    "        d=collections.defaultdict(int)\n",
    "        for i in range(n-minSize+1):\n",
    "            temp=s[i:i+minSize]\n",
    "            c=set(temp)\n",
    "            if len(c)<=maxLetters:\n",
    "                d[temp]+=1\n",
    "        return max(d.values()) if d else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        for length in range(minSize, maxSize + 1):\n",
    "            dct = defaultdict(int)\n",
    "            for i in range(length - 1, n):\n",
    "                if len(set(s[i - length + 1:i + 1])) <= maxLetters:\n",
    "                    dct[s[i - length + 1: i + 1]] += 1\n",
    "            for s in dct:\n",
    "                if s and dct[s] > res:\n",
    "                    res = dct[s]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        res = 0\n",
    "        # for size in range(minSize, maxSize + 1):\n",
    "        size = minSize\n",
    "        left = 0\n",
    "        right = size - 1\n",
    "\n",
    "        arr = [0] * 26\n",
    "        diff = 0\n",
    "        for i in range(size):\n",
    "            arr[ord(s[i]) - 97] += 1\n",
    "            if arr[ord(s[i]) - 97] == 1:\n",
    "                diff += 1\n",
    "        \n",
    "        cnts = collections.defaultdict(int)\n",
    "\n",
    "        if diff <= maxLetters:\n",
    "            cnts[s[:size]] += 1\n",
    "        \n",
    "\n",
    "        left += 1\n",
    "        right += 1\n",
    "    \n",
    "        while right < len(s):\n",
    "            arr[ord(s[right]) - 97] += 1\n",
    "\n",
    "            if arr[ord(s[right]) - 97] == 1:\n",
    "                diff += 1\n",
    "        \n",
    "            arr[ord(s[left - 1]) - 97] -= 1\n",
    "\n",
    "            if arr[ord(s[left - 1]) - 97] == 0:\n",
    "                diff -= 1\n",
    "\n",
    "            if diff <= maxLetters:\n",
    "                cnts[s[left:right + 1]] += 1\n",
    "    \n",
    "            \n",
    "            left += 1\n",
    "            right += 1\n",
    "        \n",
    "\n",
    "        res = max(res, max(cnts.values(), default = 0))\n",
    "    \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        num = 0\n",
    "        # occ = collections.defaultdict(int)\n",
    "        occ = {}\n",
    "        for i in range(0, len(s) - minSize + 1):\n",
    "            item = s[i : i + minSize]\n",
    "            print(i, item)\n",
    "            if len(set(item)) <= maxLetters:\n",
    "                if item in occ:\n",
    "                    occ[item] += 1\n",
    "                else:\n",
    "                    occ[item] = 1\n",
    "            \n",
    "                num = max(num, occ[item])\n",
    "        return num\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        c = collections.Counter()\n",
    "        for i in range(len(s)-minSize+1): c[s[i:i+minSize]] += 1\n",
    "        for k, v in c.most_common():\n",
    "            if len(set(k)) <= maxLetters: return v\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:       \n",
    "        c = collections.Counter([s[j:j+minSize] for j in range(len(s) - minSize + 1) if len(set(s[j:j+minSize])) <= maxLetters])      \n",
    "        return max(c.values()) if c else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        # 滑动窗口对于这几个约束来讲都是可行的\n",
    "        left = 0\n",
    "        letter = [0]*26\n",
    "        zhong = 0\n",
    "        hashmap = {}\n",
    "        res = -inf\n",
    "        for right in range(len(s)):\n",
    "            if letter[ord(s[right]) - ord('a')] == 0:\n",
    "                zhong += 1\n",
    "            letter[ord(s[right]) - ord('a')] += 1\n",
    "            \n",
    "            while zhong > maxLetters or right - left + 1 > maxSize:\n",
    "                letter[ord(s[left]) - ord('a')] -= 1\n",
    "                if letter[ord(s[left]) - ord('a')] == 0:\n",
    "                    zhong -= 1\n",
    "                left += 1\n",
    "            \n",
    "            while right - left + 1 > minSize:\n",
    "                if s[left:right+1] in hashmap:\n",
    "                    hashmap[s[left:right+1]] += 1\n",
    "                else:\n",
    "                    hashmap[s[left:right+1]] = 1\n",
    "                res = max(hashmap[s[left:right+1]],res)\n",
    "                # 继续缩小\n",
    "                letter[ord(s[left]) - ord('a')] -= 1\n",
    "                if letter[ord(s[left]) - ord('a')] == 0:\n",
    "                    zhong -= 1\n",
    "                left += 1\n",
    "            if minSize <= right - left + 1 <= maxSize:\n",
    "                if s[left:right+1] in hashmap:\n",
    "                        hashmap[s[left:right+1]] += 1\n",
    "                else:\n",
    "                    hashmap[s[left:right+1]] = 1\n",
    "                res = max(hashmap[s[left:right+1]],res)\n",
    "        if res < 0:\n",
    "            return 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        for i in range(minSize, maxSize + 1):\n",
    "            d = {}\n",
    "            for j in range(n - i + 1):\n",
    "                t = 0\n",
    "                for k in range(i):\n",
    "                    t |= 1 << (ord(s[j + k]) - ord('a'))\n",
    "                if t.bit_count() <= maxLetters:\n",
    "                    if not d.get(s[j : j+i] , False):\n",
    "                        d[s[j: j + i]] = 1\n",
    "                    else:\n",
    "                        d[s[j:j+i]] += 1\n",
    "            if d:\n",
    "                res = max(res, max(d.values()))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        for i in range(minSize, maxSize + 1):\n",
    "            d = {}\n",
    "            for j in range(n - i + 1):\n",
    "                t = set()\n",
    "                for k in range(i):\n",
    "                    t.add(s[j+k])\n",
    "                if len(t) <= maxLetters:\n",
    "                    if not d.get(s[j : j+i] , False):\n",
    "                        d[s[j: j + i]] = 1\n",
    "                    else:\n",
    "                        d[s[j:j+i]] += 1\n",
    "            if d:\n",
    "                res = max(res, max(d.values()))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        ss = defaultdict(int)\n",
    "        ans = 0\n",
    "        # maxSize - minSize 次滑窗\n",
    "        for k in range(minSize, maxSize + 1):\n",
    "            ss.clear()\n",
    "            mp.clear()\n",
    "            for i in range(k):\n",
    "                ss[s[i]] += 1\n",
    "            if len(ss) <= maxLetters:\n",
    "                mp[s[:k]] += 1\n",
    "            for i in range(k, len(s)):\n",
    "                c = s[i - k]\n",
    "                if ss[c] == 1:\n",
    "                    del ss[c]\n",
    "                else:\n",
    "                    ss[c] -= 1\n",
    "                ss[s[i]] += 1\n",
    "                if len(ss) <= maxLetters:\n",
    "                    mp[s[i - k + 1: i + 1]] += 1\n",
    "            if len(mp) != 0:\n",
    "                ans = max(ans, max(mp.values()))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        res = 0\n",
    "        for size in range(minSize, maxSize + 1):\n",
    "            left = 0\n",
    "            right = size - 1\n",
    "\n",
    "            arr = [0] * 26\n",
    "            diff = 0\n",
    "            for i in range(size):\n",
    "                arr[ord(s[i]) - 97] += 1\n",
    "                if arr[ord(s[i]) - 97] == 1:\n",
    "                    diff += 1\n",
    "            \n",
    "            cnts = collections.defaultdict(int)\n",
    "\n",
    "            if diff <= maxLetters:\n",
    "                cnts[s[:size]] += 1\n",
    "            \n",
    "\n",
    "            left += 1\n",
    "            right += 1\n",
    "        \n",
    "            while right < len(s):\n",
    "                arr[ord(s[right]) - 97] += 1\n",
    "\n",
    "                if arr[ord(s[right]) - 97] == 1:\n",
    "                    diff += 1\n",
    "            \n",
    "                arr[ord(s[left - 1]) - 97] -= 1\n",
    "\n",
    "                if arr[ord(s[left - 1]) - 97] == 0:\n",
    "                    diff -= 1\n",
    "\n",
    "                if diff <= maxLetters:\n",
    "                    cnts[s[left:right + 1]] += 1\n",
    "        \n",
    "                \n",
    "                left += 1\n",
    "                right += 1\n",
    "            \n",
    "\n",
    "            res = max(res, max(cnts.values(), default = 0))\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        def has_less_than_max_letters(substring, max_letters):\n",
    "            # 检查子串中不同字母的数目是否小于等于 maxLetters\n",
    "            unique_letters = set(substring)\n",
    "            return len(unique_letters) <= max_letters\n",
    "\n",
    "        substring_counts = {}  # 用于存储子串出现次数的哈希表\n",
    "        max_count = 0  # 记录出现次数最大值\n",
    "\n",
    "        # 遍历子串长度从 minSize 到 maxSize\n",
    "        for size in range(minSize, maxSize + 1):\n",
    "            # 遍历主字符串 s 中所有可能的子串\n",
    "            for i in range(len(s) - size + 1):\n",
    "                substring = s[i:i + size]\n",
    "                # 检查子串是否满足不同字母数小于等于 maxLetters\n",
    "                if has_less_than_max_letters(substring, maxLetters):\n",
    "                    # 更新子串的出现次数\n",
    "                    substring_counts[substring] = substring_counts.get(substring, 0) + 1\n",
    "                    # 更新出现次数最大值\n",
    "                    max_count = max(max_count, substring_counts[substring])\n",
    "\n",
    "        return max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        ans_dict = defaultdict(int)\n",
    "        n = len(s)\n",
    "        # 查找所有i长度的子串是否满足\n",
    "        for i in range(minSize,maxSize+1):\n",
    "            rec = defaultdict(int)\n",
    "            letters = set()\n",
    "            l = 0\n",
    "            r = i-1 \n",
    "            for j in range(l,r+1):\n",
    "                letters.add(s[j])\n",
    "                rec[s[j]]+=1           \n",
    "            set_len = len(letters)\n",
    "            # 滑动窗口\n",
    "            while(r<n):\n",
    "                # 满足条件+1\n",
    "                if(set_len<=maxLetters):\n",
    "                    ans_dict[s[l:r+1]]+=1\n",
    "                l+=1\n",
    "                r+=1\n",
    "                if r==n:\n",
    "                    break\n",
    "                letters.add(s[r])\n",
    "                if rec[s[l-1]]==1:\n",
    "                    letters.remove(s[l-1])\n",
    "                    set_len-=1\n",
    "                rec[s[l-1]]-=1\n",
    "                rec[s[r]]+=1\n",
    "                if rec[s[r]]==1:\n",
    "                    letters.add(s[r])\n",
    "                    set_len+=1\n",
    "        max_values = 0\n",
    "        for k,v in ans_dict.items():\n",
    "            max_values = max(max_values,v)\n",
    "        return max_values\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s) \n",
    "        cnt = Counter() \n",
    "        ans = 0 \n",
    "        for l in range(minSize, maxSize+1):\n",
    "            for i in range(n-l+1):\n",
    "                j = i + l - 1\n",
    "                if len(Counter(s[i:j+1])) <= maxLetters:\n",
    "                    cnt[s[i:j+1]] += 1\n",
    "                    ans = max(ans, cnt[s[i:j+1]]) \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        res, ans = 0, Counter()\n",
    "        for k in range(minSize, maxSize + 1):\n",
    "            l, d = 0, Counter()\n",
    "            for r, c in enumerate(s):\n",
    "                d[c] += 1\n",
    "                if r - l + 1 == k:\n",
    "                    if len(d) <= maxLetters:\n",
    "                        ans[s[l: r + 1]] += 1\n",
    "                        res = max(res, ans[s[l: r + 1]])\n",
    "                    d[s[l]] -= 1\n",
    "                    if d[s[l]] == 0:\n",
    "                        d.pop(s[l])\n",
    "                    l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        def has_less_than_max_letters(substring, max_letters):\n",
    "            # 检查子串中不同字母的数目是否小于等于 maxLetters\n",
    "            unique_letters = set(substring)\n",
    "            return len(unique_letters) <= max_letters\n",
    "        \n",
    "        substring_counts = {}  # 用于存储子串出现次数的哈希表\n",
    "        max_count = 0  # 记录出现次数最大值\n",
    "\n",
    "        for size in range(minSize, maxSize + 1):\n",
    "            for i in range(len(s) - size + 1):\n",
    "                substring = s[i:i + size]\n",
    "                if has_less_than_max_letters(substring, maxLetters):\n",
    "                    substring_counts[substring] = substring_counts.get(substring, 0) + 1\n",
    "                    max_count = max(max_count, substring_counts[substring])\n",
    "\n",
    "        return max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        cnt=collections.Counter()\n",
    "        n=len(s)\n",
    "        for t in range(minSize,maxSize+1):\n",
    "            for i in range(n-t+1):\n",
    "                tmp=s[i:i+t]\n",
    "              #  print(tmp)\n",
    "                p=len(set(tmp))\n",
    "               # print(p)\n",
    "                if p<=maxLetters:\n",
    "                    cnt[tmp]+=1\n",
    "        cnt[\"1\"]=0\n",
    "       #print(cnt)\n",
    "        return max(cnt.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        substring_count = {}\n",
    "        max_frequency = 0\n",
    "        \n",
    "        for size in range(minSize, maxSize + 1):\n",
    "            window = s[:size]  # 初始化滑动窗口\n",
    "            unique_letters = set(window)\n",
    "            \n",
    "            if len(unique_letters) <= maxLetters:\n",
    "                if window in substring_count:\n",
    "                    substring_count[window] += 1\n",
    "                else:\n",
    "                    substring_count[window] = 1\n",
    "                max_frequency = max(max_frequency, substring_count[window])\n",
    "            \n",
    "            # 滑动窗口，每次右移一位\n",
    "            for i in range(1, len(s) - size + 1):\n",
    "                # 移除窗口最左边的字符，添加窗口最右边的字符\n",
    "                window = s[i:i+size]\n",
    "                unique_letters = set(window)\n",
    "                \n",
    "                if len(unique_letters) <= maxLetters:\n",
    "                    if window in substring_count:\n",
    "                        substring_count[window] += 1\n",
    "                    else:\n",
    "                        substring_count[window] = 1\n",
    "                    max_frequency = max(max_frequency, substring_count[window])\n",
    "        \n",
    "        return max_frequency\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        substring_count = {}\n",
    "        max_frequency = 0\n",
    "        \n",
    "        for size in range(minSize, maxSize + 1):\n",
    "            window = s[:size]  # 初始化滑动窗口\n",
    "            unique_letters = set(window)\n",
    "            \n",
    "            if len(unique_letters) <= maxLetters:\n",
    "                if window in substring_count:\n",
    "                    substring_count[window] += 1\n",
    "                else:\n",
    "                    substring_count[window] = 1\n",
    "                max_frequency = max(max_frequency, substring_count[window])\n",
    "            \n",
    "            # 滑动窗口，每次右移一位\n",
    "            for i in range(1, len(s) - size + 1):\n",
    "                # 移除窗口最左边的字符，添加窗口最右边的字符\n",
    "                window = s[i:i+size]\n",
    "                unique_letters = set(window)\n",
    "                \n",
    "                if len(unique_letters) <= maxLetters:\n",
    "                    if window in substring_count:\n",
    "                        substring_count[window] += 1\n",
    "                    else:\n",
    "                        substring_count[window] = 1\n",
    "                    max_frequency = max(max_frequency, substring_count[window])\n",
    "        \n",
    "        return max_frequency\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        def has_less_than_max_letters(substring, max_letters):\n",
    "            # 检查子串中不同字母的数目是否小于等于 maxLetters\n",
    "            unique_letters = set(substring)\n",
    "            return len(unique_letters) <= max_letters\n",
    "        \n",
    "        substring_counts = {}  # 用于存储子串出现次数的哈希表\n",
    "        max_count = 0  # 记录出现次数最大值\n",
    "\n",
    "        for size in range(minSize, maxSize + 1):\n",
    "            for i in range(len(s) - size + 1):\n",
    "                substring = s[i:i + size]\n",
    "                if has_less_than_max_letters(substring, maxLetters):\n",
    "                    substring_counts[substring] = substring_counts.get(substring, 0) + 1\n",
    "                    max_count = max(max_count, substring_counts[substring])\n",
    "\n",
    "        return max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        res, ans = 0, Counter()\n",
    "        for k in range(minSize, maxSize + 1):\n",
    "            l, d = 0, Counter()\n",
    "            for r, c in enumerate(s):\n",
    "                d[c] += 1\n",
    "                if r - l + 1 == k:\n",
    "                    if len(d) <= maxLetters:\n",
    "                        ans[s[l: r + 1]] += 1\n",
    "                        res = max(res, ans[s[l: r + 1]])\n",
    "                    d[s[l]] -= 1\n",
    "                    if d[s[l]] == 0:\n",
    "                        d.pop(s[l])\n",
    "                    l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "f = lambda ch: ord(ch) - 97\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        cnt = defaultdict(int)\n",
    "        l = 0\n",
    "        vis = [0] * 26\n",
    "        unique = 0\n",
    "        for r, ch in enumerate(s):\n",
    "            x = f(ch)\n",
    "            if not vis[x]:\n",
    "                unique += 1\n",
    "            vis[x] += 1\n",
    "            while unique > maxLetters or r-l+1 > maxSize:\n",
    "                y = f(s[l])\n",
    "                vis[y] -= 1\n",
    "                if not vis[y]:\n",
    "                    unique -= 1\n",
    "                l += 1\n",
    "            if r-l+1 >= minSize:\n",
    "                for i in range(l, r-minSize+2):\n",
    "                    cnt[s[i:r+1]] += 1\n",
    "\n",
    "        return max(cnt.values(), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            exist = set()\n",
    "            cur = \"\"\n",
    "            for j in range(i, min(n, i + maxSize)):\n",
    "                exist.add(s[j])\n",
    "                if len(exist) > maxLetters:\n",
    "                    break\n",
    "                cur += s[j]\n",
    "                if j - i + 1 >= minSize:\n",
    "                    occ[cur] += 1\n",
    "                    ans = max(ans, occ[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "      from collections import defaultdict\n",
    "\n",
    "      freq = defaultdict(int)\n",
    "\n",
    "      n = len(s)\n",
    "      for i in range(n):\n",
    "        letters = set()\n",
    "        for j in range(maxSize):\n",
    "          if i + j >= n:\n",
    "            break\n",
    "\n",
    "          letters.add(s[i + j])\n",
    "          if len(letters) > maxLetters:\n",
    "            break\n",
    "\n",
    "          if j + 1 >= minSize:\n",
    "            freq[s[i : i + j + 1]] += 1\n",
    "\n",
    "      return 0 if not freq.values() else max(freq.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        cmap = {}\n",
    "        mapping = {}\n",
    "        result = 0\n",
    "        left, right = 0, 0\n",
    "        n = len(s)\n",
    "        while(right < n):\n",
    "            if(s[right] not in cmap):\n",
    "                cmap[s[right]] = 1\n",
    "            else:\n",
    "                cmap[s[right]] += 1\n",
    "            while(left <= right and len(cmap) > maxLetters):\n",
    "                cmap[s[left]] -= 1\n",
    "                if(cmap[s[left]] == 0):\n",
    "                    del cmap[s[left]]\n",
    "                left += 1\n",
    "            i = left\n",
    "            while(i <= right):\n",
    "                if(right - i + 1 < minSize):\n",
    "                    break\n",
    "                if(right - i + 1 <= maxSize):\n",
    "                    if(s[i:right+1] not in mapping):\n",
    "                        mapping[s[i:right+1]] = 1\n",
    "                    else:\n",
    "                        mapping[s[i:right+1]] += 1\n",
    "                    result = max(result, mapping[s[i:right+1]])\n",
    "                i += 1\n",
    "            right += 1\n",
    "        return result\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        cmap = {}\n",
    "        mapping = {}\n",
    "        result = 0\n",
    "        left, right = 0, 0\n",
    "        n = len(s)\n",
    "        while(right < n):\n",
    "            if(s[right] not in cmap):\n",
    "                cmap[s[right]] = 1\n",
    "            else:\n",
    "                cmap[s[right]] += 1\n",
    "            while(left <= right and len(cmap) > maxLetters):\n",
    "                cmap[s[left]] -= 1\n",
    "                if(cmap[s[left]] == 0):\n",
    "                    del cmap[s[left]]\n",
    "                left += 1\n",
    "            i = left\n",
    "            while(i <= right):\n",
    "                if(right - i + 1 < minSize):\n",
    "                    break\n",
    "                if(right - i + 1 <= maxSize):\n",
    "                    if(s[i:right+1] not in mapping):\n",
    "                        mapping[s[i:right+1]] = 1\n",
    "                    else:\n",
    "                        mapping[s[i:right+1]] += 1\n",
    "                    result = max(result, mapping[s[i:right+1]])\n",
    "                i += 1\n",
    "            right += 1\n",
    "        return result\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        l = 0\n",
    "        ws = collections.defaultdict(int)\n",
    "        counts = [0]*26\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            # window size [minSize, maxSize]\n",
    "            c = s[i] \n",
    "            idx = ord(c) - ord(\"a\")\n",
    "            if counts[idx] == 0:\n",
    "                cnt += 1\n",
    "            counts[idx] += 1 \n",
    "            while i - l + 1 > maxSize or cnt > maxLetters:\n",
    "                t = ord(s[l]) - ord(\"a\")\n",
    "                counts[t] -= 1\n",
    "                if counts[t] == 0: cnt -= 1\n",
    "                l += 1\n",
    "            \n",
    "            # if minSize <= i - l + 1:\n",
    "                # 应该计算以右边界为断点的子序列\n",
    "                # ws[s[l:i+1]] += 1\n",
    "                # l + ms <= i + 1\n",
    "                # l <= i - ms + 1\n",
    "\n",
    "            # [l,i] 长度不超过max 计算以i为右边界的string\n",
    "            # [i-ms+1, i] 正好是 ms \n",
    "            # print(l, i-minSize)\n",
    "            for j in range(l,i-minSize+2):\n",
    "                # [l, r]\n",
    "                ws[s[j:i+1]] += 1\n",
    "        res = 0\n",
    "        for k in ws:\n",
    "            res = max(res, ws[k])\n",
    "        return res\n",
    "\n",
    "\n",
    "        # counts = collections.defaultdict(int)\n",
    "        # for l in range(minSize, maxSize+1):\n",
    "        #     for i in range(n-l+1):\n",
    "        #         # s[i,i+l]\n",
    "        #         counts[s[i:i+l]] += 1\n",
    "        # res = 0\n",
    "        # for substr in counts:\n",
    "        #     res = max(res, counts[substr])\n",
    "        # return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        c=Counter()\n",
    "        for i,w in enumerate(s):\n",
    "            if i<minSize-1: continue\n",
    "            for j in range(max(0,i-maxSize+1),(i-minSize+1)+1):\n",
    "                nw=s[j:i+1]\n",
    "                if len(set(nw))<=maxLetters:\n",
    "                    c[nw]+=1\n",
    "        return max(c.values(),default=0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i + minSize > n: break\n",
    "            exist = set()\n",
    "            cur = ''\n",
    "            for j in range(i, min(n, i + maxSize)):\n",
    "                exist.add(s[j])\n",
    "                if len(exist) > maxLetters:\n",
    "                    break\n",
    "                cur += s[j]\n",
    "                if j - i + 1 >= minSize:\n",
    "                    occ[cur] += 1\n",
    "                    ans = max(ans, occ[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        num = 0\n",
    "        # occ = collections.defaultdict(int)\n",
    "        occ = {}\n",
    "        print(range(0, len(s) - minSize + 1))\n",
    "        for i in range(0, len(s) - minSize + 1):\n",
    "            item = \"\"\n",
    "            for j in range(i, min(len(s), i + maxSize)):\n",
    "                item += s[j]\n",
    "                if len(item) > maxSize:\n",
    "                    break\n",
    "                if len(set(item)) > maxLetters:\n",
    "                    break \n",
    "                if len(item) >= minSize:\n",
    "                    if item in occ:\n",
    "                        occ[item] += 1\n",
    "                    else:\n",
    "                        occ[item] = 1\n",
    "                    num = max(num, occ[item])\n",
    "                \n",
    "        return  num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = defaultdict(int)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            exist = set()\n",
    "            cur = \"\"\n",
    "            for j in range(i, min(n, i+maxSize)):\n",
    "                exist.add(s[j])\n",
    "                if len(exist) > maxLetters:\n",
    "                    break\n",
    "                cur += s[j]\n",
    "                if j-i+1 >= minSize:\n",
    "                    occ[cur] += 1\n",
    "                    res = max(res, occ[cur])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            exist = set()\n",
    "            cur = \"\"\n",
    "            for j in range(i, min(n, i + maxSize)):\n",
    "                exist.add(s[j])\n",
    "                if len(exist) > maxLetters:\n",
    "                    break\n",
    "                cur += s[j]\n",
    "                if j - i + 1 >= minSize:\n",
    "                    occ[cur] += 1\n",
    "                    ans = max(ans, occ[cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        num = 0\n",
    "        occ = collections.defaultdict(int)\n",
    "        print(range(0, len(s) - minSize + 1))\n",
    "        for i in range(0, len(s) - minSize + 1):\n",
    "            item = \"\"\n",
    "            for j in range(i, min(len(s), i + maxSize)):\n",
    "                item += s[j]\n",
    "                if len(item) > maxSize:\n",
    "                    break\n",
    "                if len(set(item)) > maxLetters:\n",
    "                    break \n",
    "                if len(item) >= minSize:\n",
    "                    occ[item] += 1\n",
    "                    num = max(num, occ[item])\n",
    "                \n",
    "        return  num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        count_dict = {}\n",
    "        for i in range(len(s)):\n",
    "            for length in range(minSize, maxSize+1):\n",
    "                if i + length <= len(s):\n",
    "                    sub = s[i:i+length]\n",
    "                    if len(set(sub)) <= maxLetters:\n",
    "                        count_dict[sub] = count_dict.get(sub, 0) + 1\n",
    "        if len(count_dict) == 0:\n",
    "            return 0\n",
    "        return max(count_dict.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        c=collections.Counter()\n",
    "        n=len(s)\n",
    "        def check(s):\n",
    "            c1=collections.Counter(s)\n",
    "            #print(s,c1,len(c1.keys()))\n",
    "            if len(c1.keys())<=maxLetters:\n",
    "                c[s]+=1\n",
    "        for i in range(n):\n",
    "            for j in range(i+minSize,i+maxSize+1):\n",
    "                if j>n:\n",
    "                    break\n",
    "                #print(i,j,s[i:j])\n",
    "                check(s[i:j])\n",
    "        #print(c)\n",
    "        if not c:\n",
    "            return 0\n",
    "        return max(c[key] for key in c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            exist = set()\n",
    "            cur = \"\"\n",
    "            for j in range(i, min(n, i + maxSize)):\n",
    "                exist.add(s[j])\n",
    "                if len(exist) > maxLetters:\n",
    "                    break\n",
    "                cur += s[j]\n",
    "                if j - i + 1 >= minSize:\n",
    "                    occ[cur] += 1\n",
    "                    ans = max(ans, occ[cur])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n",
    "        n = len(s)\n",
    "        occ = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            st = set()\n",
    "\n",
    "            cur = \"\"\n",
    "            for j in range(i, min(n, i+maxSize)):\n",
    "                st.add(s[j])\n",
    "                if len(st) > maxLetters:\n",
    "                    break\n",
    "                cur += s[j]\n",
    "                if j - i + 1 >= minSize:\n",
    "                    occ[cur] += 1\n",
    "                    ans = max(ans, occ[cur])\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
